package com.tql.oneday;

public class test01 {
    public static void main(String[] args) {
        int []arr={1,4,2,5,0,10};
        int []arr1={1,2,3,4,5,6,8};
       /* insertSort(arr);
        System.out.println((int)(Math.random()*(7-1)));*/
        binarySearch(arr1,8);
    }
    public static void insertSort(int []arr){
        for (int i=1;i<arr.length;i++){
            for (int j = i-1; j>=0&&arr[j]>arr[j+1] ; j--) {
                swap(arr,j,j+1);
            }
        }

    }
    //i和j物理地址是同一个的话会报错
    public static void swap(int []arr,int i,int j){
        arr[i]=arr[i]^arr[j];
        arr[j]=arr[i]^arr[j];
        arr[i]=arr[i]^arr[j];
    }
    public static void insertSort1(int []arr){
        for (int i=1;i<arr.length;i++){
            for (int j = i-1; j>=0&&arr[j]>arr[j+1]; j--) {
                swap(arr,j,j+1);
            }
        }

    }
    //二分查找算法 时间复杂度 0（log2N）折半原理
    public static void binarySearch(int []arr,int target){
        insertSort(arr);
        int left=0;
        int right=arr.length-1;
        if(target>arr[arr.length-1]||target<arr[0]){
            System.out.println("超出查询范围");
            return;
        }
        while(left<=right){
            int t=(left+right)/2;

            if(target>arr[t]){
                left=t+1;
            }
            if(target<arr[t]){
                right=t-1;
            }
            if(target==arr[t]){
                System.out.println(true);
                System.out.println(arr[t]);
                break;
            }
        }

    }
}
